module nade.quadmap;

import std.stdio;
import std.math;

import derelict.opengl.gl;

import nade.vector;


class QuadMap {
	this()
	{
		_quad = new Quad(null, Quad.Child.NN);
		_x1 = _y1 = 0;
		_x2 = _y2 = 1;
	}

	private {
		Quad	_quad;
		int		_x1, _y1;
		int		_x2, _y2;
	}
}


class Quad {
	enum Child {
		NN = 0,
		NP = 1,
		PN = 2,
		PP = 3,
	}

	this(Quad parent, Child child)
	{
		_parent = parent;
		_child = child;
	}

	void render()
	{
		foreach(locator, b; _contents)
			locator.render();

		foreach(child; _children)
			if(child !is null)
				child.render();
	}

	private {
		Quad		_parent;
		Child		_child;

		Quad		_children[4];

		bool[Locator]	_contents;
	}
}


class Locator {
	this(QuadMap map, const Vector2 position, const Vector2 size, void delegate() render_dg)
	{
		_quad = map._quad;
		_x1 = map._x1;
		_y1 = map._y1;
		_x2 = map._x2;
		_y2 = map._y2;

		_position = position.dup;
		_size = size.dup;
		_render_dg = render_dg;

		_quad._contents[this] = true;

		update(_position - _size*0.5, _position + _size*0.5);
	}

	void render()
	{
		if(_render_dg !is null)
		{
			glPushMatrix();
			_position.applyTranslation();
			_render_dg();
			glPopMatrix();
		}
	}

	void renderQuad()
	{
		_quad.render();
	}

	void move(const Vector2 to)
	{
		_position = to.dup;
		update(_position - _size*0.5, _position + _size*0.5);
	}
	void move(const Vector2 to, const Vector2 size)
	{
		_size = size.dup;
		move(to);
	}

	private {
		void update(int x1, int y1, int x2, int y2)
		{
			// writefln("update: %d %d %d %d", x1, y1, x2, y2);
start:
			if(x1 < _x1)
			{
				if(y1 < _y1)
					expand(Quad.Child.PP);
				else
					expand(Quad.Child.PN);

				goto start;
			}

			if(y1 < _y1)
			{
				expand(Quad.Child.NP);

				goto start;
			}

			if(x2 >= _x2)
			{
				if(y2 >= _y2)
					expand(Quad.Child.NN);
				else
					expand(Quad.Child.NP);

				goto start;
			}

			if(y2 >= _y2)
			{
				expand(Quad.Child.PN);

				goto start;
			}

middle:
			if((_x2 - _x1) <= 1  ||  (_y2 - _y1) <= 1) return;

			const mx = (_x1 + _x2)/2;
			const my = (_y1 + _y2)/2;
			if(x2 < mx)
			{
				if(y2 < my)
				{
					shrink(Quad.Child.NN);
					goto middle;
				}
				else if(y1 >= my)
				{
					shrink(Quad.Child.NP);
					goto middle;
				}
			}
			else if(x1 >= mx)
			{
				if(y2 < my)
				{
					shrink(Quad.Child.PN);
					goto middle;
				}
				else if(y1 >= my)
				{
					shrink(Quad.Child.PP);
					goto middle;
				}
			}
		}
		void update(Vector2 p1, Vector2 p2)
		{
			update(cast(int)floor(p1.x), cast(int)floor(p1.y), cast(int)floor(p2.x), cast(int)floor(p2.y));
		}

		void shrink(Quad.Child child)
		{
			_quad._contents.remove(this);

			auto c = _quad._children[child];
			if(c is null)
			{
				c = _quad._children[child] = new Quad(_quad, child);
			}

			switch(child)
			{
				case Quad.Child.NN: _x2 = (_x1 + _x2)/2; _y2 = (_y1 + _y2)/2; break;
				case Quad.Child.NP: _x2 = (_x1 + _x2)/2; _y1 = (_y1 + _y2)/2; break;
				case Quad.Child.PN: _x1 = (_x1 + _x2)/2; _y2 = (_y1 + _y2)/2; break;
				case Quad.Child.PP: _x1 = (_x1 + _x2)/2; _y1 = (_y1 + _y2)/2; break;

				default: assert(false);
			}

			assert((_x2 - _x1) >= 1);
			assert((_y2 - _y1) >= 1);

			_quad = c;
			_quad._contents[this] = true;

			// writefln("shrink: %d %d %d %d", _x1, _y1, _x2, _y2);
		}

		void expand(Quad.Child child)
		{
			_quad._contents.remove(this);

			auto c = _quad._parent;
			if(c is null)
			{
				c = _quad._parent = new Quad(null, Quad.Child.NN);
				_quad._child = child;
				c._children[child] = _quad;
			}

			switch(_quad._child)
			{
				case Quad.Child.NN: _x2 = _x2*2 - _x1; _y2 = _y2*2 - _y1; break;
				case Quad.Child.NP: _x2 = _x2*2 - _x1; _y1 = _y1*2 - _y2; break;
				case Quad.Child.PN: _x1 = _x1*2 - _x2; _y2 = _y2*2 - _y1; break;
				case Quad.Child.PP: _x1 = _x1*2 - _x2; _y1 = _y1*2 - _y2; break;

				default: assert(false);
			}

			_quad = c;
			_quad._contents[this] = true;

			// writefln("expand: %d %d %d %d", _x1, _y1, _x2, _y2);
		}
	}

	Quad quad() { return _quad; }

	int x1() { return _x1; }
	int y1() { return _y1; }
	int x2() { return _x2; }
	int y2() { return _y2; }

	Vector2 position() { return _position; }

	Vector2 size() { return _position; }

	private {
		int			_x1, _y1, _x2, _y2;
		Quad		_quad;

		Vector2				_position;
		Vector2				_size;
		void delegate()		_render_dg;
	}
}
